package com.sparrow.common.ai.findpath.impl;

import com.sparrow.common.ai.findpath.GroupNode;
import com.sparrow.common.ai.findpath.Point;
import java.util.*;

/**
 * 图的广度优先搜索算法，所有方向均等的探索
 */
public class BreadthFirst {
    /**
     * 边界
     */
    private LinkedList<Point> frontier = new LinkedList<>();
    /**
     * 到达列表
     */
    private Set<Point> reached = new HashSet<>();
    /**
     * 邻居
     */
    private List<Point> neighbors = new ArrayList<>(4);
    /**
     * 来源
     */
    private Map<Point, Point> cameFroms = new HashMap<>();
    /**
     * 起点
     */
    private Point start;
    /**
     * 目标点
     */
    private Point goal;

    private List<GroupNode> gnList = new ArrayList<>();

    public void start(int[][] mapData, Point start, Point goal) {
        frontier.add(start);
        reached.add(start);
        this.goal = goal;
        this.start = start;
        while (!frontier.isEmpty()) {
            Point point = frontier.removeFirst();
            GroupNode gn = new GroupNode();
            gn.setParent(new int[] {point.getX(), point.getY()});
            gnList.add(gn);
            for (Point n : neighbors(mapData, point)) {
                if (!reached.contains(n)) {
                    gn.getNeighbors().add(new int[] {n.getX(), n.getY()});
                    frontier.add(n);
                    reached.add(n);
                    cameFroms.put(n, point);
                    if (n.equals(goal)) {
                        break;
                    }
                }
            }
        }
    }

    public List<Point> neighbors(int[][] mapData, Point start) {
        neighbors.clear();
        int x = start.getX();
        int y = start.getY();
        if (y - 1 >= 0) {
            neighbors.add(new Point(x, y - 1));
        }
        if (x - 1 >= 0) {
            neighbors.add(new Point(x - 1, y));
        }
        if (y + 1 < mapData.length) {
            neighbors.add(new Point(x, y + 1));
        }
        if (x + 1 < mapData[0].length) {
            neighbors.add(new Point(x + 1, y));
        }
        return neighbors;
    }

//    public static void main(String[] args) {
//        int[][] mapData = new int[10][10];
//        for (int i = 0; i < 10; i++) {
//            for (int j = 0; j < 10; j++) {
//                mapData[i][j] = 0;
//            }
//        }
//        MapFrame mapFrame = new MapFrame(mapData);
//
//        BreadthFirst breadthFirst = new BreadthFirst();
//        Point start = new Point(0, 0);
//        Point goal = new Point(5, 5);
//
//        mapFrame.mapPanel.setStart(start.toIntArray());
//        mapFrame.mapPanel.setEnd(goal.toIntArray());
//
//        breadthFirst.start(mapData, start, goal);
//
//        Point pre = goal;
//        LinkedList<Point> paths = new LinkedList<>();
//        paths.add(pre);
//        while (pre != null && !pre.equals(start)) {
//            pre = breadthFirst.cameFroms.get(pre);
//            paths.add(pre);
//        }
//
//        Collections.reverse(paths);
//
//        List<int[]> pathList = paths.stream().map(e -> e.toIntArray()).collect(Collectors.toList());
//        mapFrame.mapPanel.setPaths(pathList);
//        mapFrame.mapPanel.setExplores(breadthFirst.gnList);
//    }
}
